/*
 * @lc app=leetcode.cn id=51 lang=cpp
 *
 * [51] N 皇后
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        n_ = n;
        rowFlag_.resize(n, 0);
        colFlag_.resize(n, 0);
        diagRightFlag_.resize(2*n-1, 0);
        diagLeftFlag_.resize(2*n-1, 0);

        std::string emptyRow(n, '.');
        currentChessBoard_.resize(n, emptyRow);

        traceBack(0, 0);

        return result_;
    }
private:
    void traceBack(int row, int col) {
// showChessBoard();
        if (queenCounter_ == n_) {
            result_.emplace_back(currentChessBoard_);
            return;
        }

        for (int index = row*n_+col;index<n_*n_;++index) {
            int i = index / n_;
            int j = index % n_;

            if (checkCellValid(i, j)) {
                setCellStatus(i, j, 1);
                currentChessBoard_[i][j] = 'Q';
                queenCounter_ += 1;

                traceBack(i+1, 0);                

                queenCounter_ -= 1;
                currentChessBoard_[i][j] = '.';
                setCellStatus(i, j, -1);
            }
        }
    }
    inline bool checkCellValid(int row, int col) {
        // 3 4 5 6
        // 2 3 4 5
        // 1 2 3 4
        // 0 1 2 3
        int rightDiag = n_ - 1 - row + col;
        // 0 1 2 3
        // 1     4
        // 2     5
        // 3 4 5 6
        int leftDiag = row + col;
        return rowFlag_[row] == 0 and
               colFlag_[col] == 0 and
               diagRightFlag_[rightDiag] == 0 and
               diagLeftFlag_[leftDiag] == 0;
    }
    inline void setCellStatus(int row, int col, int status) {
        int rightDiag = n_ - 1 - row + col;
        int leftDiag = row + col;
        rowFlag_[row] += status;
        colFlag_[col] += status;
        diagRightFlag_[rightDiag] += status;
        diagLeftFlag_[leftDiag] += status;
    }
private:
    vector<vector<string>> result_;
    vector<string> currentChessBoard_;
    string testStr = "abcde";
private:
    int n_;
    int queenCounter_ = 0;
    // row ??? useless ~
    std::vector<int> rowFlag_;
    std::vector<int> colFlag_;
    std::vector<int> diagRightFlag_;
    std::vector<int> diagLeftFlag_;
private:
    void showChessBoard() {
        printf("--------\n");
        for (int i=0;i<n_;++i) {
            printf("%s\n", currentChessBoard_[i].c_str());
        }
        printf("--------\n");
        for (int i=0;i<n_;++i) {
            for (int j=0;j<n_;++j) {
                if (checkCellValid(i, j)) {
                    printf("0");
                } else {
                    printf("1");
                }
            }
            printf("\n");
        }
    }
};
// @lc code=end

int main() {
    Solution test;
    test.solveNQueens(3);
}
